package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月18日
*时间：上午11:39:46
*/
public class Q69 {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> rs = new ArrayList<>();
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()) {
        	List<TreeNode> tmp = new ArrayList<>();
        	List<Integer> result = new ArrayList<>();
            for (TreeNode t : list) {
                result.add(t.val);
                if (t.left != null) {
                    tmp.add(t.left);
                }
                if (t.right != null) {
                    tmp.add(t.right);
                }
            }
            rs.add(result);
            list = tmp;
        }
        return rs;
    }

    @Test
    public void testA() {
        TreeNode root = new TreeNode(0);
        TreeNode r1 = new TreeNode(1);
        TreeNode r2 = new TreeNode(2);
        TreeNode r3 = new TreeNode(3);
        TreeNode r4 = new TreeNode(4);
        TreeNode r5 = new TreeNode(5);
        root.left = r1;
        root.right = r2;
        r1.left = r3;
        r2.right = r5;
        r3.right = r4;

        List<List<Integer>> rs = levelOrder(root);
        for (List<Integer> a : rs) {
            System.out.println(a);
        }
    }
}
